"""
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？
在真实的面试中遇到过这道题？
"""
# Definition for a binary tree node.


class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def preorderTraversal(self, root):
        """
        一路向左然后从最下面的子节点开始打开向上
        :param root:
        :return:
        """
        if not root: return []
        stack = []
        res = []
        while root or stack:
            while root:
                stack.append(root)
                res.append(root.val)
                root = root.left
            node = stack.pop()
            root = node.right
        return res

    def midorderTraversal(self, root):
        """
        还是先从左入栈，然后每弹出一个栈顶元素就存下来然后压入右子节点
        :param root:
        :return:
        """
        if not root: return []
        stack = []
        res = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            node = stack.pop()
            res.append(node.val)
            root = node.right
        return res

    def postorderTraversal(self, root):
        """
        核心思想：倒叙来先左后右倒叙出栈阅后即焚
        :param root:
        :return:
        """
        if not root: return []
        stack = [root]
        res =[]
        while stack:
            top = stack.pop()
            if top.left: stack.append(top.left)
            if top.right: stack.append(top.right)
            res.append(top.val)
        return res[::-1]


if __name__ == '__main__':
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n1.right = n2
    n2.left = n3
    s = Solution()
    print(s.postorderTraversal(n1))
